{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Most Stones Removed with Same Row or Column"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #union-find #graph #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #并查集 #图 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeStones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移除最多的同行或同列石头"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code> 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。</p>\n",
    "\n",
    "<p>如果一块石头的 <strong>同行或者同列</strong> 上有其他石头存在，那么就可以移除这块石头。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code> 的数组 <code>stones</code> ，其中 <code>stones[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 表示第 <code>i</code> 块石头的位置，返回 <strong>可以移除的石子</strong> 的最大数量。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>一种移除 5 块石头的方法如下所示：\n",
    "1. 移除石头 [2,2] ，因为它和 [2,1] 同行。\n",
    "2. 移除石头 [2,1] ，因为它和 [0,1] 同列。\n",
    "3. 移除石头 [1,2] ，因为它和 [1,0] 同行。\n",
    "4. 移除石头 [1,0] ，因为它和 [0,0] 同列。\n",
    "5. 移除石头 [0,1] ，因为它和 [0,0] 同行。\n",
    "石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>一种移除 3 块石头的方法如下所示：\n",
    "1. 移除石头 [2,2] ，因为它和 [2,0] 同行。\n",
    "2. 移除石头 [2,0] ，因为它和 [0,0] 同列。\n",
    "3. 移除石头 [0,2] ，因为它和 [0,0] 同行。\n",
    "石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [[0,0]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>[0,0] 是平面上唯一一块石头，所以不可以移除它。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= stones.length <= 1000</code></li>\n",
    "\t<li><code>0 <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>4</sup></code></li>\n",
    "\t<li>不会有两块石头放在同一个坐标点上</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [most-stones-removed-with-same-row-or-column](https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [most-stones-removed-with-same-row-or-column](https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]', '[[0,0],[0,2],[1,1],[2,0],[2,2]]', '[[0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class UnionFind:\n",
    "#     def __init__(self, n):\n",
    "#         self.fa = [i for i in range(n)]\n",
    "#         self.count = n\n",
    "#     def find(self, x):\n",
    "#         if x != self.fa[x]:\n",
    "#             self.fa[x] = self.find(self.fa[x])\n",
    "#         return self.fa[x]\n",
    "#     def union(self, x, y):\n",
    "#         root_x = self.find(x)\n",
    "#         root_y = self.find(y)\n",
    "#         if root_x == root_y:\n",
    "#             return False\n",
    "#         self.fa[root_x] = root_y\n",
    "#         self.count -= 1\n",
    "#         return True\n",
    "#     def is_connected(self, x, y):\n",
    "#         return self.find(x) == self.find(y)\n",
    "\n",
    "# class Solution:\n",
    "#     def removeStones(self, stones: List[List[int]]) -> int:\n",
    "#         size = len(stones)\n",
    "#         uf = UnionFind(size)\n",
    "#         for i in range(size):\n",
    "#             for j in range(i+1, size):\n",
    "#                 if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:\n",
    "#                     uf.union(i, j)\n",
    "#         return size - uf.count\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.fa = dict()\n",
    "        self.cnt = n\n",
    "    def find(self, x):\n",
    "        if x not in self.fa:\n",
    "            self.cnt += 1\n",
    "            self.fa[x] = x\n",
    "        if x != self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return \n",
    "        self.fa[root_x] = root_y\n",
    "        self.cnt -= 1\n",
    "        \n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        uf = UnionFind(0)\n",
    "        n = len(stones)\n",
    "        for i in range(n):\n",
    "            uf.union(stones[i][0] + 10001, stones[i][1])\n",
    "        return n - uf.cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n = len(stones)\n",
    "        ufs = list(range(n))\n",
    "        def find(x):\n",
    "            return x if ufs[x] == x else find(ufs[x])\n",
    "        def union(x, y):\n",
    "            X, Y = find(x), find(y)\n",
    "            if X == Y:\n",
    "                return False\n",
    "            ufs[X] = Y\n",
    "            return True\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:\n",
    "                    if union(i, j):\n",
    "                        cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        m = 0\n",
    "        row = collections.defaultdict(set)\n",
    "        col = collections.defaultdict(set)\n",
    "        for i, j in stones:\n",
    "            row[i] |= {j}\n",
    "            col[j] |= {i}\n",
    "            m = max(m, i)\n",
    "\n",
    "        graph = 0\n",
    "        for i in range(m + 1):\n",
    "            if i in row:\n",
    "                graph += 1\n",
    "                stack = {i}\n",
    "\n",
    "                while stack:\n",
    "                    x = stack.pop()\n",
    "                    for j in row[x]:\n",
    "                        if j in col:\n",
    "                            stack |= col[j]\n",
    "                            del col[j]\n",
    "                    del row[x]\n",
    "        return len(stones) - graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UFS():\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        xr = self.find(x)\n",
    "        yr = self.find(y)\n",
    "        self.p[xr] = yr\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        ufs = UFS(20000)\n",
    "        for x, y in stones:\n",
    "            ufs.union(x, y + 10001)\n",
    "        return len(stones) - len({ufs.find(x) for x, y in stones})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n = len(stones)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        degress = [0]*n\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if stones[i][0] == stones[j][0] or stones[i][1]==stones[j][1]:\n",
    "                    graph[i].append(j)\n",
    "                    graph[j].append(i)\n",
    "                    degress[i] += 1\n",
    "                    degress[j] += 1\n",
    "        moved = set()\n",
    "        def dfs(node):\n",
    "            if node in moved:\n",
    "                return\n",
    "            moved.add(node)\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in moved:\n",
    "                    dfs(neighbor)\n",
    "        cnt = 0\n",
    "        for node in range(n):\n",
    "            if node not in moved:\n",
    "                cnt +=  1\n",
    "                dfs(node)\n",
    "        return len(moved)-cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n=len(stones)\n",
    "        edge=collections.defaultdict(list)\n",
    "        res=collections.defaultdict(list)\n",
    "        for i,(x,y) in enumerate(stones):\n",
    "            res[x].append(i)\n",
    "            res[y+10001].append(i)\n",
    "\n",
    "        for vec in res.values():\n",
    "            k=len(vec)\n",
    "            for i in range(1,k):\n",
    "                edge[vec[i-1]].append(vec[i])\n",
    "                edge[vec[i]].append(vec[i-1])\n",
    "        \n",
    "        def dfs(x):\n",
    "            vis.add(x)\n",
    "            for y in edge[x]:\n",
    "                if y not in vis:\n",
    "                    dfs(y)\n",
    "        \n",
    "        vis=set()\n",
    "        num=0\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                num+=1\n",
    "                dfs(i)\n",
    "        return n-num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        map = dict()\n",
    "        cnt = 1\n",
    "        N = 2 * 10 ** 3\n",
    "        p = list(range(N))\n",
    "        components = len(stones)\n",
    "        def find(x):\n",
    "            if p[x] != x: p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def get(x, y):\n",
    "            nonlocal cnt\n",
    "            if (x, y) not in map:\n",
    "                map[(x, y)] = cnt\n",
    "                cnt += 1\n",
    "            return map[(x, y)]\n",
    "        row, col = defaultdict(list), defaultdict(list)\n",
    "        ans = 0\n",
    "        for x, y in stones:\n",
    "            a = get(x, y)\n",
    "            flag = False\n",
    "            for b in row[x]:\n",
    "                pa, pb = find(a), find(b)\n",
    "                if pa != pb:\n",
    "                    p[pa] = pb\n",
    "                    ans += 1\n",
    "            for b in col[y]:\n",
    "                pa, pb = find(a), find(b)\n",
    "                if pa != pb:\n",
    "                    p[pa] = pb\n",
    "                    ans += 1\n",
    "            row[x].append(a)\n",
    "            col[y].append(a)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "# 方法一：并查集\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.count = n\n",
    "    \n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        self.parent[root_x] = root_y\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connect(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        size = len(stones)\n",
    "        n = 10010\n",
    "        union_find = UnionFind(2 * n)\n",
    "        for stone in stones:\n",
    "            x = stone[0]\n",
    "            y = stone[1] + n\n",
    "            union_find.union(x, y)\n",
    "\n",
    "        stones_set = set()\n",
    "        for stone in stones:\n",
    "            stones_set.add(union_find.find(stone[0]))\n",
    "        return size - len(stones_set)\n",
    "'''\n",
    "\n",
    "# 方法二：深度优先搜索——递归\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        def dfs(i):\n",
    "            visited.add(i)\n",
    "            for j in edge[i]:\n",
    "                if j not in visited:\n",
    "                    dfs(j)\n",
    "        \n",
    "        edge = collections.defaultdict(list)\n",
    "        for i, (x1, y1) in enumerate(stones):\n",
    "            for j, (x2, y2) in enumerate(stones):\n",
    "                if x1 == x2 or y1 == y2:\n",
    "                    edge[i].append(j)\n",
    "        \n",
    "        ans = 0\n",
    "        visited = set()\n",
    "        n = len(stones)\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                dfs(i)\n",
    "                ans += 1\n",
    "        return n - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        indices = defaultdict(list)\n",
    "        stones.sort(key = lambda x:x[0])\n",
    "\n",
    "        for i in range(len(stones)):\n",
    "            cur = i+1\n",
    "            while cur< len(stones) and stones[cur][0]==stones[i][0]:\n",
    "                indices[(stones[cur][0],stones[cur][1])].append((stones[i][0],stones[i][1]))\n",
    "                indices[(stones[i][0],stones[i][1])].append((stones[cur][0],stones[cur][1]))\n",
    "                cur+=1\n",
    "\n",
    "        stones.sort(key = lambda x:x[1])\n",
    "\n",
    "        for i in range(len(stones)):\n",
    "            cur = i+1\n",
    "            while cur< len(stones) and stones[cur][1]==stones[i][1]:\n",
    "                indices[(stones[cur][0],stones[cur][1])].append((stones[i][0],stones[i][1]))\n",
    "                indices[(stones[i][0],stones[i][1])].append((stones[cur][0],stones[cur][1]))\n",
    "                cur+=1    \n",
    "\n",
    "        num = 0\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(x):\n",
    "            visited.add(x)\n",
    "            for y in indices[x]:\n",
    "                if y not in visited:\n",
    "                    dfs(y)\n",
    "\n",
    "        for i in range(len(stones)):\n",
    "            if (stones[i][0],stones[i][1]) not in visited:\n",
    "                num+=1\n",
    "                dfs((stones[i][0],stones[i][1]))\n",
    "        \n",
    "        return len(stones)-num\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        record, visited, result = {}, {}, 0\n",
    "        for i in range(len(stones)):\n",
    "            record[(stones[i][0], stones[i][1])] = []\n",
    "            visited[(stones[i][0], stones[i][1])] = False\n",
    "            for j in range(len(stones)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if stones[j][0] == stones[i][0] or stones[j][1] == stones[i][1]:\n",
    "                    record[(stones[i][0], stones[i][1])].append((stones[j][0], stones[j][1]))\n",
    "        def dfs(stone):\n",
    "            if visited[(stone[0], stone[1])] == True:\n",
    "                return\n",
    "            visited[(stone[0], stone[1])] = True\n",
    "            for nextstone in record[(stone[0], stone[1])]:\n",
    "                dfs(nextstone)\n",
    "        for stone in stones:\n",
    "            if visited[(stone[0], stone[1])] != True:\n",
    "                dfs(stone)\n",
    "                result += 1\n",
    "        return len(stones) - result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        dict_X=collections.defaultdict(list)\n",
    "        dict_Y=collections.defaultdict(list)\n",
    "        for x,y in stones:\n",
    "            dict_X[x].append((x,y))\n",
    "            dict_Y[y].append((x,y))\n",
    "        visited=set()\n",
    "\n",
    "        def dfs(node):\n",
    "            if node in visited:return\n",
    "            visited.add(node)\n",
    "            x,y=node\n",
    "            for newnode in dict_X[x]:\n",
    "                dfs(newnode)\n",
    "            for newnode in dict_Y[y]:\n",
    "                dfs(newnode)\n",
    "            \n",
    "        ans=0\n",
    "        for node in stones:\n",
    "            node=tuple(node)\n",
    "            if node not in visited:\n",
    "                ans+=1\n",
    "                dfs(node)\n",
    "        return len(stones)-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        dict_x = defaultdict(list)\n",
    "        dict_y = defaultdict(list)\n",
    "\n",
    "        for x, y in stones:\n",
    "            dict_x[x].append((x, y))\n",
    "            dict_y[y].append((x, y))\n",
    "\n",
    "        visited = set()\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            if (x, y) in visited:\n",
    "                return\n",
    "\n",
    "            visited.add((x, y)) \n",
    "            for i, j in dict_x[x]:\n",
    "                dfs(i, j)\n",
    "            \n",
    "            for i, j in dict_y[y]:\n",
    "                dfs(i, j)\n",
    "        \n",
    "        res = 0\n",
    "        for x, y in stones:\n",
    "            if (x, y) not in visited:\n",
    "                res += 1\n",
    "                dfs(x, y)\n",
    "\n",
    "        return len(stones) - res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: list[list[int]]) -> int:\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        \n",
    "        graph = defaultdict(list)\n",
    "        for x1, y1 in stones:\n",
    "            for x2, y2 in stones:\n",
    "                if x1 == x2 and y1 == y2:\n",
    "                    continue\n",
    "                if x1 == x2 or y1 == y2:\n",
    "                    graph[(x1, y1)].append((x2, y2))\n",
    "                    graph[(x2, y2)].append((x1, y1))\n",
    "        \n",
    "        visited = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            visited.add(node)\n",
    "            for n in graph[node]:\n",
    "                if n not in visited:\n",
    "                    dfs(n)\n",
    "        \n",
    "        connected = 0\n",
    "        for x, y in stones:\n",
    "            node = (x, y)\n",
    "            if node not in visited:\n",
    "                connected += 1\n",
    "                dfs(node)\n",
    "        \n",
    "        return len(stones) - connected\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        # parent=list(range(len(stones)))\n",
    "        # def find(x):\n",
    "        #     if parent[x]==x:\n",
    "        #         return x\n",
    "        #     parent[x]=find(parent[x])\n",
    "        #     return parent[x]\n",
    "        # def union(x,y):\n",
    "        #     t1=find(x)\n",
    "        #     t2=find(y)\n",
    "        #     if t1!=t2:\n",
    "        #         parent[t1]=t2\n",
    "        # for i in range(len(stones)):\n",
    "        #     for j in range(i+1,len(stones)):\n",
    "        #         if stones[i][0]==stones[j][0] or stones[i][1]==stones[j][1]:\n",
    "        #             union(i,j)\n",
    "        # res=0\n",
    "        # tmp=set()\n",
    "        # for i in range(len(stones)):\n",
    "        #     tmp.add(find(i))\n",
    "        # return len(stones)-len(tmp)\n",
    "        parent=[-1]*20002\n",
    "        def find(x):\n",
    "            if parent[x]==-1:\n",
    "                return x\n",
    "            parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            t1=find(x)\n",
    "            t2=find(y)\n",
    "            if t1!=t2:\n",
    "                parent[t1]=t2\n",
    "        for i,j in stones:\n",
    "            union(i,j+10001)\n",
    "        tmp=set()\n",
    "        for i in range(len(stones)):\n",
    "            tmp.add(find(stones[i][0]))\n",
    "        return len(stones)-len(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "\n",
    "        length = len(stones)\n",
    "\n",
    "        maxRow = 0\n",
    "        # 构造一个图\n",
    "        graph = [[0 for _ in range(length)] for _ in range(length)]\n",
    "        for i in range(length):\n",
    "            for j in range(i, length):\n",
    "                if stones[i][0] == stones[j][0]  or stones[i][1] == stones[j][1]:\n",
    "                    graph[i][j] = 1\n",
    "                    graph[j][i] = 1\n",
    "                    if maxRow < i:\n",
    "                        maxRow = i\n",
    "\n",
    "        \n",
    "        queue = []\n",
    "        \n",
    "        count = 0\n",
    "        res = 0\n",
    "        visited = [0] * length\n",
    "        # dfs\n",
    "        for i in range(maxRow):\n",
    "            if visited[i] == 0:\n",
    "                count = 0\n",
    "                visited[i] = 1\n",
    "                queue.append(i)\n",
    "                \n",
    "                while len(queue) > 0:\n",
    "                    tmp = queue.pop(0)\n",
    "                    count += 1\n",
    "                    for j in range(length):\n",
    "                        if graph[tmp][j] == 1 and visited[j] == 0:\n",
    "                            visited[j] = 1\n",
    "                            queue.append(j)\n",
    "                res += (count - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n = len(stones)\n",
    "        adj = [None] * n\n",
    "        for i in range(n):\n",
    "            adj[i] = [0] * n\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:\n",
    "                    adj[i][j], adj[j][i] = 1, 1\n",
    "        \n",
    "        from collections import deque\n",
    "        def bfs(node):\n",
    "            _visited = [node]\n",
    "            que = deque([node])\n",
    "            while que:\n",
    "                new_node = que.popleft()\n",
    "                for i in range(n):\n",
    "                    if adj[new_node][i] and i not in _visited:\n",
    "                        que.append(i)\n",
    "                        _visited.append(i)\n",
    "            return _visited\n",
    "        \n",
    "        visited = []\n",
    "        connect = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                connect += 1\n",
    "                visited.extend(bfs(i))\n",
    "        return n - connect\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UFS():\n",
    "    def __init__(self,N):\n",
    "        self.p=[i for i in range(N)]\n",
    "\n",
    "    def find(self,x):\n",
    "        if self.p[x]!=x:\n",
    "            self.p[x]=self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "    \n",
    "    def union(self,x,y):\n",
    "        xr=self.find(x)\n",
    "        yr=self.find(y)\n",
    "        self.p[xr]=yr\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        #连通区域数量\n",
    "        ufs= UFS(200000)\n",
    "        for x,y in stones:\n",
    "            ufs.union(x,y+100000)\n",
    "        return len(stones)-len({ufs.find(x) for x,y in stones})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "\n",
    "    def find(self, k):\n",
    "        if self.root[k] == k:\n",
    "            return k\n",
    "        self.root[k] = self.find(self.root[k])\n",
    "        return self.root[k]\n",
    "\n",
    "    def union(self, a, b):\n",
    "        x,y = self.find(a), self.find(b)\n",
    "        if x != y: self.root[x] = y\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n = len(stones)\n",
    "        dsu = DSU(n)\n",
    "        transfer_matrix = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]: dsu.union(i,j)\n",
    "        ans = set()        \n",
    "        for i in range(n):\n",
    "            ans.add(dsu.find(i))\n",
    "        return n - len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Uf:\n",
    "    def __init__(self, n):\n",
    "        self.count = n\n",
    "        self.parent = []\n",
    "        for i in range(n):\n",
    "            self.parent.append(i)\n",
    "    \n",
    "    def find(self, p):\n",
    "        if self.parent[p] != p:\n",
    "            self.parent[p] = self.find(self.parent[p])\n",
    "        return self.parent[p]\n",
    "    \n",
    "    def union(self, p, q):\n",
    "        root_p = self.find(p)\n",
    "        root_q = self.find(q)\n",
    "        if root_p == root_q:\n",
    "            return \n",
    "        self.parent[root_p] = root_q\n",
    "        self.count -= 1\n",
    "    \n",
    "    def count(self):\n",
    "        return self.count\n",
    "\n",
    "       \n",
    "class Solution:\n",
    "    def check_is_connect(self, stone1, stone2):\n",
    "        if stone1[0] == stone2[0] or stone1[1] == stone2[1]:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n = len(stones)\n",
    "        uf = Uf(n)\n",
    "        graph = [[False for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if self.check_is_connect(stones[i], stones[j]):\n",
    "                    graph[i][j] = True\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if graph[i][j]:\n",
    "                    uf.union(i, j)\n",
    "        return n - uf.count\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        size = max(max(_[0] for _ in stones), max(_[1] for _ in stones))\n",
    "        p = list(range(size+10001))  # 初始化根节点为自身,因为最大为10000,就加10001.\n",
    "        rank = [1 for _ in range(size+10001)]  # 初始高度设为1\n",
    "\n",
    "        def get_root(x):\n",
    "            if p[x] != p[p[x]]:\n",
    "                p[x] = get_root(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def union(r, c):\n",
    "            r_root = get_root(r)\n",
    "            c_root = get_root(c)\n",
    "            if rank[r_root] == rank[c_root]:  # 压缩路径,合并连通的行列.\n",
    "                p[r_root] = c_root\n",
    "                rank[c_root] += 1\n",
    "            elif rank[r_root] < rank[c_root]:\n",
    "                p[r_root] = c_root\n",
    "            else:\n",
    "                p[c_root] = r_root\n",
    "\n",
    "        n = len(stones)\n",
    "        for r, c in stones:\n",
    "            union(r, c+10000)  # [[0,1],[1,0]]  需要将行列分隔开.\n",
    "        return n - len({get_root(_[0]) for _ in stones})\n",
    "\n",
    "        # p = list(range(20000))\n",
    "        # rank = [1 for _ in range(20000)]\n",
    "\n",
    "        # def get_root(x):\n",
    "        #     if p[x] != p[p[x]]:\n",
    "        #         p[x] = get_root(p[x])\n",
    "        #     return p[x]\n",
    "\n",
    "        # def union(r, c):\n",
    "        #     r_root = get_root(r)\n",
    "        #     c_root = get_root(c)\n",
    "        #     if rank[r_root] == rank[c_root]:\n",
    "        #         p[r_root] = c_root\n",
    "        #         rank[c_root] += 1\n",
    "        #     elif rank[r_root] < rank[c_root]:\n",
    "        #         p[r_root] = c_root\n",
    "        #     else:\n",
    "        #         p[c_root] = r_root\n",
    "\n",
    "        # n = len(stones)\n",
    "        # for r, c in stones:\n",
    "        #     union(r, c+10000)\n",
    "\n",
    "        # return n - len({get_root(r) for r, c in stones})\n",
    "\n",
    "        # p = []\n",
    "        # checked = set()\n",
    "        # for i, e in enumerate(stones):\n",
    "        #     x, y = {e[0]}, {e[1]}  # 行列集合\n",
    "        #     if (e[0], e[1]) not in checked:\n",
    "        #         cnt = 0\n",
    "        #         while True:\n",
    "        #             add_new = False  # 用于检查行列有没有新加入,如果有新加入,就要遍历检查.\n",
    "        #             for j in stones[i + 1:]:\n",
    "        #                 a, b = j[0], j[1]\n",
    "        #                 if (a, b) not in checked:\n",
    "        #                     if a in x or b in y:\n",
    "        #                         x.add(a)\n",
    "        #                         y.add(b)\n",
    "        #                         cnt += 1  # 每加一入一个新点,计数+1.\n",
    "        #                         checked.add((a, b))\n",
    "        #                         add_new = True\n",
    "        #             if not add_new:\n",
    "        #                 break\n",
    "        #         p.append((e[0], e[1], cnt))\n",
    "        # return sum(_[2] for _ in p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        hash_table = dict()\n",
    "        nums = len(stones)\n",
    "        for i in range(nums):\n",
    "            deps = []\n",
    "            for j in range(nums):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if stones[i][0] == stones[j][0]:\n",
    "                    deps.append(j)\n",
    "                elif stones[i][1] == stones[j][1]:\n",
    "                    deps.append(j)\n",
    "            hash_table[i] = deps\n",
    "        max_count = 0\n",
    "        visited = list()\n",
    "        travel = list()\n",
    "        for num in hash_table:\n",
    "            if num in visited:\n",
    "                continue\n",
    "            visited.append(num)\n",
    "            travel.append(num)\n",
    "            while len(travel):\n",
    "                max_count += 1\n",
    "                node = travel[0]\n",
    "                travel.pop(0)\n",
    "                for v_node in hash_table[node]:\n",
    "                    if v_node not in visited:\n",
    "                        visited.append(v_node)\n",
    "                        travel.append(v_node)\n",
    "            max_count -= 1\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        self.p=list(range(20000))\n",
    "        def find(x):\n",
    "            if x!=self.p[x]:\n",
    "                self.p[x]=find(self.p[x])\n",
    "            return self.p[x]\n",
    "        def union(x,y):\n",
    "            xr=find(x)\n",
    "            yr=find(y)\n",
    "            self.p[xr]=yr\n",
    "            return\n",
    "        for x,y in stones:\n",
    "            union(x,y+10000)\n",
    "        return len(stones)-len({find(x) for x,y in stones})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        V = [ [] for i in range(100000)]\n",
    "        n = len(stones)\n",
    "        ans = 0\n",
    "        vis = [0]*n\n",
    "\n",
    "        def dfs(i):\n",
    "            if vis[i]==1:\n",
    "                return \n",
    "            vis[i] = 1\n",
    "            x,y = stones[i]\n",
    "            for t in V[x]:\n",
    "                dfs(t)\n",
    "            \n",
    "            for t in V[y+10005]:\n",
    "                dfs(t)\n",
    "\n",
    "        for i in range(len(stones)):\n",
    "            x,y = stones[i]\n",
    "            V[x].append(i)\n",
    "            V[y+10005].append(i)\n",
    "        \n",
    "        for i in range(len(stones)):\n",
    "            if not vis[i]:\n",
    "                ans+=1\n",
    "                dfs(i)\n",
    "        \n",
    "        return n-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        def findfather(x):\n",
    "            if father[x] == x:\n",
    "                return x\n",
    "            fa_x = findfather(father[x])\n",
    "            father[x] = fa_x\n",
    "            return fa_x\n",
    "\n",
    "        MAXN = 10010\n",
    "        father = list(range(MAXN << 1))\n",
    "        counts = defaultdict(int)\n",
    "        num_stones = len(stones)\n",
    "        for i in range(num_stones):\n",
    "            x, y = stones[i]\n",
    "            father[findfather(x)] = findfather(y + MAXN)\n",
    "        for i in range(num_stones):\n",
    "            counts[findfather(stones[i][0])] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for value in counts.values():\n",
    "            ans += value - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if parent[x]!=x:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(a,b):\n",
    "            parent[find(a)]=find(b)\n",
    "        n=10002\n",
    "        parent=[i for i in range(2*n)]\n",
    "        for i,j in stones:\n",
    "            union(i,j+n)\n",
    "        root=set()\n",
    "        for i,j in stones:\n",
    "            root.add(find(i))\n",
    "        return len(stones)-len(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n=10010\n",
    "        parent=list(range(2*n))\n",
    "        # 并查集查找\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        # 合并\n",
    "        def union(i,j):\n",
    "            parent[find(i)]=find(j)            \n",
    "        # 连通横纵坐标\n",
    "        for i,j in stones:\n",
    "            union(i,j+n)\n",
    "        # 获取连通区域的根节点\n",
    "        root=set()\n",
    "        for i,j in stones:\n",
    "            root.add(find(i))\n",
    "        return len(stones)-len(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n=10010\n",
    "        parent=list(range(2*n))\n",
    "        # 并查集查找\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        # 合并\n",
    "        def union(i,j):\n",
    "            parent[find(i)]=find(j)            \n",
    "        # 连通横纵坐标\n",
    "        for i,j in stones:\n",
    "            union(i,j+n)\n",
    "        # 获取连通区域的根节点\n",
    "        root=set()\n",
    "        for i,j in stones:\n",
    "            root.add(find(i))\n",
    "        return len(stones)-len(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: [[int]]) -> int:\n",
    "        parent = [i for i in range(20001)]\n",
    "\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            parent[find(y)] = find(x)\n",
    "\n",
    "        for n1, n2 in stones:\n",
    "            n2 = n2 + 10001\n",
    "            union(n2, n1)\n",
    "        root = {find(x) for x, y in stones}\n",
    "        return len(stones) - len(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        p = [0] * 20005\n",
    "        \n",
    "        def find(i):\n",
    "            if i != p[i]:\n",
    "                p[i] = find(p[i])\n",
    "            return p[i]\n",
    "            \n",
    "        def union(i, j):\n",
    "            p[find(j)] = find(i)\n",
    "\n",
    "        # 初始化\n",
    "        for i in range(20005):\n",
    "            p[i] = i\n",
    "        \n",
    "        # 合并\n",
    "        for stone in stones:\n",
    "            x, y = stone[0], stone[1] + 10001\n",
    "            # x, y 本身也就是一个点\n",
    "            union(x, y)\n",
    "\n",
    "        # 查找\n",
    "        res = set()\n",
    "        for stone in stones:\n",
    "            res.add(find(stone[0]))\n",
    "        \n",
    "        return len(stones) - len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        #print('===========',stones)\n",
    "        l=len(stones)\n",
    "        if l<=1:\n",
    "            return 0\n",
    "        # tmp={}\n",
    "        # xs=set([i[0] for i in stones])\n",
    "        # ys=set([i[1] for i in stones])\n",
    "        # tmpx={}\n",
    "        # tmpy={}\n",
    "        # for x in xs:\n",
    "        #     tmpx[x]=len([i for i in stones if i[0]==x])\n",
    "        # for y in ys:\n",
    "        #     tmpy[y]=len([i for i in stones if i[1]==y])\n",
    "        \n",
    "        # tmp=[]\n",
    "        # for i in range(len(stones)):\n",
    "        #     v=stones[i]\n",
    "        #     if tmpx[v[0]]==1 and tmpy[v[1]]==1:\n",
    "        #         stones.pop(i)\n",
    "        #         return self.removeStones(stones)\n",
    "        #     tmp.append(tmpx[v[0]]+tmpy[v[1]])\n",
    "        # i=tmp.index(min(tmp))\n",
    "        # print('==========',len(stones),i,stones)\n",
    "        \n",
    "        # print(stones.pop(i))\n",
    "        # return 1+self.removeStones(stones)\n",
    "\n",
    "        # tmpx=[stones[0][0]]\n",
    "        # tmpy=[stones[0][1]]\n",
    "        # l=len(stones)\n",
    "        # stones_=stones[1:].copy()\n",
    "        # k=1\n",
    "        # for i in range(1,l):\n",
    "        #     if stones[i][0] in tmpx or stones[i][1] in tmpy:\n",
    "        #         tmpx.append(stones[i][0])\n",
    "        #         tmpy.append(stones[i][1])\n",
    "        #         #print(stones_)\n",
    "        #         #print(stones[i],stones_)\n",
    "        #         stones_.pop(stones_.index(stones[i]))\n",
    "        #         #print(stones[i],stones_)\n",
    "        #         k+=1\n",
    "        # return k+self.removeStones(stones_)\n",
    "        n=10001\n",
    "        fa=[i for i in range(n*2)]\n",
    "        def find(i):\n",
    "            if fa[i]==i:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i]=find(fa[i])\n",
    "                return fa[i]\n",
    "            return \n",
    "\n",
    "        def union(i,j):\n",
    "            fa[find(i)]=find(j)\n",
    "            return \n",
    "\n",
    "        for i,j in stones:\n",
    "            union(i,j+n)    \n",
    "        ans=set()\n",
    "        for i,j in stones:\n",
    "            ans.add(find(i))\n",
    "        return len(stones)-len(ans)\n",
    "        # for i in range(l):\n",
    "        #     for j in range(i,l):\n",
    "        #         if stones[i][0]==stones[j][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones) -> int:\n",
    "        def find(node):\n",
    "            if parents[node] != node:\n",
    "                parents[node] = find(parents[node])\n",
    "            return parents[node]\n",
    "\n",
    "        def union(node1, node2):\n",
    "            parents[find(node2)] = find(node1)\n",
    "\n",
    "        # x + y各自最多10001个取值,这创建一个20005大小的数组\n",
    "        parents = [i for i in range(20005)]\n",
    "        for x, y in stones:\n",
    "            union(x, y + 10001)\n",
    "\n",
    "        res = set()\n",
    "        for ele in stones:\n",
    "            if parents[ele[0]] == ele[0]:\n",
    "                res.add(ele[0])\n",
    "        return len(stones) - len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n = len(stones)\n",
    "        p = [i for i in range(20002)]\n",
    "        \n",
    "        def findroot(a):\n",
    "            if p[a] != a:\n",
    "                p[a] = findroot(p[a])\n",
    "            return p[a]\n",
    "        \n",
    "        for i,j in stones:\n",
    "            a = findroot(i)\n",
    "            b = findroot(j+10001)\n",
    "            if a != b:\n",
    "                p[max(a,b)] = min(a,b)\n",
    "\n",
    "        sum = 0\n",
    "        dic = set()\n",
    "        for i,j in stones:\n",
    "            root = findroot(i)\n",
    "            if root not in dic:\n",
    "                sum += 1\n",
    "                dic.add(root)\n",
    "        return n-sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n=10010\n",
    "        parent=list(range(2*n))\n",
    "        def find(x:int):\n",
    "            if(x!=parent[x]):\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(index1:int,index2:int):\n",
    "            parent[find(index1)]=find(index2)\n",
    "        for i,j in stones:\n",
    "            union(i,j+n)\n",
    "        root=set()\n",
    "        for i,j in stones:\n",
    "            root.add(find(i))\n",
    "        return len(stones)-len(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        father = [i for i in range(20000)]\n",
    "        def find(a):\n",
    "            if father[a]!=a:\n",
    "                father[a] = find(father[a])\n",
    "            return father[a]\n",
    "        def union(a,b):\n",
    "            father[find(a)] = find(b)\n",
    "        \n",
    "        for x,y in stones:\n",
    "            union(x,y+10000)\n",
    "        for x,y in stones:\n",
    "            find(y+10000)\n",
    "        return len(stones) - len({father[y+10000] for x,y in stones})\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        \n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def union(x, y):\n",
    "            p[find(x)] = find(y)\n",
    "\n",
    "        N = len(stones)\n",
    "        p = [i for i in range(20000)]\n",
    "        for x, y in stones:\n",
    "            union(x, y + 10000)\n",
    "        print([find(x) for x, y in stones])\n",
    "        return N - len({find(x) for x, y in stones})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n=10010\n",
    "        parent=list(range(n*2))\n",
    "        def find(index:int):\n",
    "            if parent[index]!=index:\n",
    "                parent[index]=find(parent[index])\n",
    "            return parent[index]\n",
    "        def union(index1:int,index2:int):\n",
    "            root1=find(index1)\n",
    "            root2=find(index2)\n",
    "            if root1==root2:\n",
    "                return\n",
    "            else:\n",
    "                parent[find(index1)]=find(index2)\n",
    "        for i,j in stones:\n",
    "            union(i,j+n)\n",
    "        root=set()\n",
    "        for i,j in stones:\n",
    "            root.add(find(i))\n",
    "        return len(stones)-len(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        ufs = list(range(20000))\n",
    "\n",
    "        def root(a):\n",
    "            if ufs[a] != a:\n",
    "                ufs[a] = root(ufs[a])\n",
    "            return ufs[a]\n",
    "\n",
    "        def union(a, b):\n",
    "            ra = root(a)\n",
    "            rb = root(b)\n",
    "            ufs[ra] = rb\n",
    "\n",
    "        for x, y in stones:\n",
    "            union(x, y + 10000)\n",
    "\n",
    "        return len(stones) - len({root(x) for x, y in stones})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    parent = {}\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if x == self.parent[x]:\n",
    "                return x\n",
    "            self.parent[x] = find(self.parent[x])\n",
    "            return self.parent[x] \n",
    "        self.parent = list(range(20000))\n",
    "        def union(x, y):\n",
    "            self.parent[find(x)] = find(y)\n",
    "        for x,y in stones:\n",
    "            union(x, y+10000)\n",
    "        \n",
    "        return len(stones) - len({find(x) for x,y in stones})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    parent = {}\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if x == self.parent[x]:\n",
    "                return x\n",
    "            self.parent[x] = find(self.parent[x])\n",
    "            return self.parent[x] \n",
    "        self.parent = list(range(20000))\n",
    "        def union(x, y):\n",
    "            self.parent[find(x)] = find(y)\n",
    "        for x,y in stones:\n",
    "            union(x, y+10000)\n",
    "        \n",
    "        return len(stones) - len({find(x) for x,y in stones})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    p = []\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        def ini(N):\n",
    "            self.p = [i for i in range(N)]\n",
    "\n",
    "        def find(x):\n",
    "            if self.p[x] != x:\n",
    "                self.p[x] = find(self.p[x])\n",
    "            return self.p[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            xr = find(x)\n",
    "            yr = find(y)\n",
    "            self.p[xr] = yr\n",
    "        \n",
    "        ini(20000)\n",
    "        for x,y in stones:\n",
    "            union(x, y+10000)\n",
    "        return len(stones)-len({find(x) for x,y in stones})\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        p = list(range(20000))\n",
    "        def root(pos):\n",
    "            if p[pos] != pos:\n",
    "                p[pos] = root(p[pos])\n",
    "            return p[pos]\n",
    "\n",
    "        for x, y in stones:\n",
    "            xr = root(x)\n",
    "            yr = root(y + 10000)\n",
    "            p[xr] = yr\n",
    "        \n",
    "        return len(stones) - len({root(x) for x, y in stones})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        p = {i:i for i in range(20000)}\n",
    "        def f(x):\n",
    "            if x != p[x]:\n",
    "                p[x] = f(p[x])\n",
    "            return p[x]\n",
    "        \n",
    "        for x, y in stones:\n",
    "            px, py = f(x), f(y+10000)\n",
    "            p[py] = px\n",
    "        \n",
    "        res = set()\n",
    "        for i, j in stones:\n",
    "            res.add(f(i))\n",
    "        return len(stones) - len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n=10001\n",
    "        parent={i:i for i in range(2*n)}\n",
    "        def find_root(x):\n",
    "            if parent[x]!=x:\n",
    "                parent[x]=find_root(parent[x])\n",
    "            return parent[x]\n",
    "        \n",
    "        def union(x,y):\n",
    "            x_root=find_root(x)\n",
    "            y_root=find_root(y)\n",
    "            if x_root!=y_root:\n",
    "                parent[x_root]=y_root \n",
    "\n",
    "        for x,y in stones:\n",
    "            union(x,y+n)\n",
    "\n",
    "        s=set()\n",
    "        for x,y in stones:\n",
    "            s.add(find_root(x))\n",
    "        return len(stones)-len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        F = [*range(20000)]\n",
    "        def find(x):\n",
    "            if F[x] != x:\n",
    "                F[x] = find(F[x])\n",
    "            return F[x]\n",
    "        def union(x,y):\n",
    "            F[find(x)] = find(y)\n",
    "        \n",
    "        for i,j in stones:\n",
    "            union(i,j+10000)\n",
    "        \n",
    "        return len(stones) - len({find(i) for i,j in stones})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def removeStones(self, stones):\n",
    "        num = len(stones)\n",
    "        def makeSet(N):\n",
    "            return [i for i in range(N)]\n",
    "        \n",
    "        def find(x):\n",
    "            if dsu[x]!=x:\n",
    "                dsu[x] = find(dsu[x])\n",
    "            return dsu[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            fx = find(x)\n",
    "            fy = find(y)\n",
    "            dsu[fx] = fy\n",
    "            \n",
    "        dsu = makeSet(20000)\n",
    "        for x, y in stones:\n",
    "            union(x, y + 10000)\n",
    "    \n",
    "        return num - len({find(x) for x, y in stones})\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        # 把所有行和列的坐标，都连通起来\n",
    "\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        \n",
    "        pa = list(range(0, 20005))\n",
    "\n",
    "        for x,y in stones:\n",
    "            a, b = find(x), find(y+10001)\n",
    "            pa[a] = b # 合并起来\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        cnt = Counter()\n",
    "        for x,y in stones:\n",
    "            cnt[find(x)] += 1\n",
    "            cnt[find(y+10001)] += 1\n",
    "        return len(stones) - len(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        n=10010\n",
    "        parent=list(range(2*n))\n",
    "        # 并查集查找\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        # 合并\n",
    "        def union(i,j):\n",
    "            parent[find(i)]=find(j)            \n",
    "        # 连通横纵坐标\n",
    "        for i,j in stones:\n",
    "            union(i,j+n)\n",
    "        # 获取连通区域的根节点\n",
    "        root=set()\n",
    "        for i,j in stones:\n",
    "            root.add(find(i))\n",
    "        return len(stones)-len(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        self.dp = [i for i in range(20000)]\n",
    "        def find(i):\n",
    "            if self.dp[i] != i:\n",
    "                self.dp[i] = find(self.dp[i])\n",
    "            return self.dp[i]\n",
    "        def merge(i, j):\n",
    "            i_index = find(i)\n",
    "            j_index = find(j)\n",
    "            self.dp[i_index] = j_index\n",
    "        \n",
    "        for i in range(len(stones)):\n",
    "            merge(stones[i][0], stones[i][1]+10000)\n",
    "        s = set()\n",
    "        for i in range(len(stones)):\n",
    "            # s.add(self.dp[i])\n",
    "            s.add(find(stones[i][0]))\n",
    "            # s.add(find(stones[i][1]+len(stones)))\n",
    "        # print(s, len(stones))\n",
    "        return len(stones) - len(s)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeStones(self, stones: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        m = len(stones)\n",
    "        b_stone = copy.deepcopy(stones)\n",
    "        temp = []\n",
    "        for item in range(m):\n",
    "            temp.append(stones[item][0])\n",
    "        del_list = []\n",
    "        for pos in range(m-1,-1,-1):\n",
    "            if temp[pos] in temp[:pos]:\n",
    "                del_list.append(pos)\n",
    "        \n",
    "        for i in del_list:\n",
    "            del stones[i]\n",
    "        final_a = len(del_list)\n",
    "        \n",
    "        temp = []\n",
    "        n = len(stones)\n",
    "        for item in range(n):\n",
    "            temp.append(stones[item][1])\n",
    "        del_list = []\n",
    "        for pos in range(n-1,-1,-1):\n",
    "            if temp[pos] in temp[:pos]:\n",
    "                del_list.append(pos)\n",
    "        final_a += len(del_list)\n",
    "\n",
    "########\n",
    "        temp = []\n",
    "        n = len(b_stone)\n",
    "        for item in range(n):\n",
    "            temp.append(b_stone[item][1])\n",
    "        del_list = []\n",
    "        for pos in range(n-1,-1,-1):\n",
    "            if temp[pos] in temp[:pos]:\n",
    "                del_list.append(pos)\n",
    "        final_b = len(del_list)\n",
    "        for i in del_list:\n",
    "            del b_stone[i]\n",
    "\n",
    "        print(b_stone)\n",
    "        temp = []\n",
    "        m = len(b_stone)\n",
    "        for item in range(m):\n",
    "            temp.append(b_stone[item][0])\n",
    "        del_list = []\n",
    "        for pos in range(m-1,-1,-1):\n",
    "            if temp[pos] in temp[:pos]:\n",
    "                del_list.append(pos)\n",
    "        final_b += len(del_list)\n",
    "        print(final_a,final_b)\n",
    "        return max(final_a, final_b)\n",
    "        \"\"\"\n",
    "        n=10010\n",
    "        parent=list(range(2*n))\n",
    "        # 并查集查找\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        # 合并\n",
    "        def union(i,j):\n",
    "            parent[find(i)]=find(j)            \n",
    "        # 连通横纵坐标\n",
    "        for i,j in stones:\n",
    "            union(i,j+n)\n",
    "        # 获取连通区域的根节点\n",
    "        root=set()\n",
    "        for i,j in stones:\n",
    "            root.add(find(i))\n",
    "        return len(stones)-len(root)\n",
    "\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
